package Algorithm.String.TrieTree;

import java.util.*;
//https://leetcode-cn.com/problems/concatenated-words/
//472. 连接词
public class Leetcode472_notice_连接词 {

    /**
     * 前缀树 + dfs
     */
    class Solution {
        Trie root = new Trie();
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> result = new ArrayList<String>();
            Arrays.sort(words,(a,b)->(a.length() - b.length()));
            for(String s : words){
                if(s.length() == 0){
                    continue;
                }
                if(dfs(s, 0)){
                    result.add(s);
                }else{
                    insert(s);
                }
            }

            return result;
        }

        public boolean dfs(String s, int start){
            Trie node = root;
            if (s.length() == start) {
                return true;
            }
            for(int i = start; i < s.length(); i++){
                char c = s.charAt(i);
                node = node.children[c - 'a'];
                if(node == null){
                    return false;
                }
                if(node.isEnd){
                    boolean r = dfs(s, i+1);
                    if(r){
                        return true;
                    }
                }
            }
            return false;
        }


        public void insert(String s){
            Trie node = root;
            for(int i = 0; i < s.length(); i++){
                if(node.children[s.charAt(i) - 'a'] == null){
                    node.children[s.charAt(i) - 'a'] = new Trie();
                }
                node = node.children[s.charAt(i) - 'a'];
            }

            node.isEnd = true;
        }

        class Trie{
            Trie[] children;
            boolean isEnd;
            Trie(){
                children = new Trie[26];
                isEnd = false;
            }
        }
    }


}
